class Solution {
    /**
     * dp[i] 表示 s{0,i-1} 能否拆分
     * 如果d[j] 能拆分 而且 s.substring(j,i)存在set中 那么d[i]为true
     */
    public boolean wordBreak(String s, List<String> wordDict) {

        // list --> set 查找时间复杂度为O(1)
        Set<String> st = new HashSet<>(wordDict);

        int len = s.length();
        boolean[] dp = new boolean[len+10];
        dp[0] = true;

        s = " "+s;
        for (int i = 1; i <= len+1; i++) {
            for (int j = 0; j <= i-1; j++) {
//                System.out.format("(%s)",s.substring(j+1,i));
                // 如果能拆分
                if( dp[j]==true &&  st.contains(s.substring(j+1,i))){
                    dp[i-1] = true;
                }
            }
        }
//        System.out.println(Arrays.toString(dp));
        return dp[len];
    }
}